package com.example.sword;

import java.util.ArrayList;

public class Test62 {

    public static void main(String[] args) {
        System.out.println("haha");
    }

    public class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;

        TreeNode(int val) {
            this.val = val;
        }


    }


    /**
     *
     * 给定一棵二叉搜索树，请找出其中的第k小的结点。
     *
     * 二叉搜索树（左<根<右）
     *
     */

    //递归
    TreeNode KthNode(TreeNode pRoot, int k){

        int index = 0;

        if (pRoot!=null){
            TreeNode root = KthNode(pRoot.left,k);
            if (root!=null)
                return root;
            //每root==null  一次 就按从小到大顺序遍历出来一个
            index++;
            if(index==k){
                return pRoot;
            }
            root = KthNode(pRoot.right,k);
            if (root!=null)
                return root;
        }

        //当root==null 时不进行循环 返回null
        return null;
    }
    //非递归
//    TreeNode KthNode2(TreeNode pRoot, int k){
//
//    }
}
